package com.mlh.dp.knapsackProblem;

//一和零
// 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
// 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集
//
// 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
// 输出：4
// 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
// 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

public class FindMaxForm {
    public static void main(String[] args) {
        //String[]strs={"10","0","1"};
        String[]strs={"10","0001","111001","1","0"};
        System.out.println(method2(strs,5,3));
    }


    //读题思路：m和n好似两个背包  字符串数组里面就是物品  这边的最终目的是装下最多的字符串
    //思路就是 加一个字符串进来  拿还是不拿  就这样

    //暴力递归
    public static int method1(String[] strs, int m, int n){
        return process(strs,m,n,strs.length-1);
    }
    public static int process(String[] strs, int m, int n,int pos){
        if(pos<0){
            return 0;
        }
        int m0=0;
        int n1=0;
        for (char c : strs[pos].toCharArray()) {
            if(c=='1'){
                n1++;
            }else{
                m0++;
            }
        }
        if(m-m0<0||n-n1<0){
            return process(strs,m,n,pos-1);
        }else{
            return Math.max(process(strs,m-m0,n-n1,pos-1)+1,process(strs,m,n,pos-1)) ;
        }
    }

    //记忆搜索
    public static int method2(String[] strs, int m, int n){
        int[][][]dp=new int[strs.length][m+1][n+1];
        for(int i=0;i<strs.length;i++){
            for(int j=0;j<=m;j++){
                for(int k=0;k<=n;k++){
                    dp[i][j][k]=-1;
                }
            }
        }
        return process1(strs,m,n,strs.length-1,dp);

    }

    public static int process1(String[] strs, int m, int n,int pos,int[][][]dp){
        if(pos<0){
            return 0;
        }
        if(dp[pos][m][n]!=-1){
            return dp[pos][m][n];
        }
        int m0=0;
        int n1=0;
        for (char c : strs[pos].toCharArray()) {
            if(c=='1'){
                n1++;
            }else{
                m0++;
            }
        }
        if(m-m0<0||n-n1<0){
            dp[pos][m][n]=process(strs,m,n,pos-1);
            return dp[pos][m][n];
        }else{
            dp[pos][m][n]=Math.max(process(strs,m-m0,n-n1,pos-1)+1,process(strs,m,n,pos-1)) ;
            return dp[pos][m][n];
        }
    }

    //严格表依赖
    public static int method3(String[] strs, int m, int n){
        int[][][]dp=new int[strs.length+1][m+1][n+1];

        for(int i=1;i<=strs.length;i++){
            int m0=0;
            int n1=0;
            for (char c : strs[i-1].toCharArray()) {
                if(c=='1'){
                    n1++;
                }else{
                    m0++;
                }
            }
            for(int j=0;j<=m;j++){
                for(int k=0;k<=n;k++){
                    if(j-m0<0||k-n1<0){
                        dp[i][j][k]=dp[i-1][j][k];
                    }else{
                        dp[i][j][k]=Math.max(dp[i-1][j-m0][k-n1]+1,dp[i-1][j][k]) ;
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }


}
